home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / c / library / dos / diverses / leda / incl / ch_hashi.h < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  4.0 KB  |  169 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  ch_hashing.h
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17.  
  18.  
  19. //------------------------------------------------------------------------------
  20. // Hashing with Chaining
  21. // 
  22. // Walter Zimmer   (1989)
  23. //------------------------------------------------------------------------------
  24.  
  25. #ifndef CHHASHINGH
  26. #define CHHASHINGH
  27.  
  28. #include <LEDA/basic.h>
  29. #include <LEDA/list.h>
  30.  
  31. #define NOTEST
  32.  
  33. #ifdef TEST
  34. #define TRACE(x)  cout << form x
  35. #define TRACE2(x,ebene)  if ( debug >= (ebene) ) cout << form  x
  36. #define TRACE_FUNC(x) x
  37. // extern int debug ; muss im testprogramm definiert werden , falls
  38. // Trace2(x,ebene) benutzt wird
  39. #else 
  40. #define TRACE(x) 
  41. #define TRACE2(x,ebene) 
  42. #define TRACE_FUNC(x) 
  43. #endif
  44.  
  45.  
  46. //--------------------------------------------------------------------
  47. // some declarations and type definitions
  48. //--------------------------------------------------------------------
  49.  
  50.  
  51. class ch_hashing_el {
  52.   ent k;
  53.   ent e;
  54.   friend class ch_hashing;
  55.  
  56.   public:
  57.  
  58.   ch_hashing_el(ch_hashing_el* p)     
  59.   { 
  60.     k = p->k; 
  61.     e = p->e; 
  62.    }
  63.  
  64.   ch_hashing_el(ent K = 0, ent E = 0) 
  65.   { 
  66.     k = K; 
  67.     e = E; 
  68.    }
  69.  
  70.   OPERATOR_NEW(2)
  71.   OPERATOR_DEL(2)
  72.  
  73. };
  74.  
  75. typedef ch_hashing_el* list2_el;
  76. declare(list,list2_el);
  77. typedef list(list2_el) hash_list;
  78. typedef hash_list* hash_list_ptr;
  79.  
  80. typedef int (*hash_fct) (ent&);
  81.  
  82. extern int default_hash_fct(ent&);
  83.  
  84. const int default_hash_tablesize = 1000;
  85.  
  86. //--------------------------------------------------------------------
  87. // class ch_hashing
  88. //--------------------------------------------------------------------
  89.  
  90. class ch_hashing {
  91.   
  92.    hash_list_ptr* hash_table;
  93.    int table_size;           
  94.    int divisor;   // divisor = 2^n-1 = 00..0011.11  
  95.                   // => statt " modulo table_size " einfach " & divisor"
  96.    hash_fct f;
  97.    hash_list_ptr* iterator;
  98.    int counter;
  99.  
  100.    int round(int) const;
  101.    hash_list_ptr* get_list(ent) const;
  102.    list_item      get_list_el(ent,hash_list*) const;
  103.    void new_size_or_fct(int, hash_fct);
  104.  
  105.    virtual int cmp(ent& x, ent& y) const { return int(x) - int(y); }
  106.    virtual void clear_key(ent& x)  const { x=0; }
  107.    virtual void clear_inf(ent& x)  const { x=0; }
  108.    virtual void copy_key(ent& x)   const { x=x; }
  109.    virtual void copy_inf(ent& x)   const { x=x; }
  110.    virtual void print_key(ent& x)  const { cout << int(x); }
  111.  
  112.    public:
  113.  
  114.    ch_hashing_el* lookup(ent) const;
  115.    ch_hashing_el* insert(ent,ent);
  116.    ch_hashing_el* del(ent);
  117.  
  118.    bool member(ent x)   const  { return ( lookup(x) ? true : false ); } 
  119.  
  120.    ent& access(ent);
  121.  
  122.    ent  key(ch_hashing_el* p)  const { return p->k; }
  123.    ent  inf(ch_hashing_el* p)  const { return p->e; }
  124.    ent& info(ch_hashing_el* p)       { return p->e; }
  125.  
  126.    bool change_obj(ent x, ent y);
  127.    void change_inf( ch_hashing_el* p , ent y) { copy_inf(p->e = y) ; }
  128.  
  129.    bool empty()  const { return counter ? false : true ; } 
  130.    int   size()  const { return counter; } 
  131.  
  132.    int  tablesize() const { return table_size ; }
  133.  
  134.    void print() const ;
  135.  
  136.    float average_list_length()  const { return float(counter) / table_size ; }
  137.  
  138.    void init_iterator();
  139.  
  140.    ch_hashing_el* move_iterator();
  141.  
  142.    void new_table_size(int Tablesize) { new_size_or_fct(Tablesize,f); }
  143.  
  144.    void new_hash_fct(hash_fct F)      { new_size_or_fct(table_size,F); }
  145.  
  146.    void new_size_and_fct(int Tablesize ,hash_fct F)
  147.                                       { new_size_or_fct(Tablesize,F); }
  148.  
  149.    void clear();
  150.    void remove();
  151.  
  152.    ch_hashing();
  153.    ch_hashing(int);
  154.    ch_hashing(hash_fct);
  155.    ch_hashing(int,hash_fct);
  156.  
  157.    ~ch_hashing() { remove(); }    //  neben clear auch remove implem.
  158.  
  159. };  // end of class ch_hashing
  160.  
  161.  
  162.  
  163. #define forall_in_ch_hashing(k,t)\
  164. for( (t).init_iterator() ; (k)=(t).move_iterator() ; )
  165.  
  166.  
  167.  
  168. #endif CHHASHINGH
  169.